// #include<iostream>
// #include<cstring>
// #include<cassert>
// #include<algorithm>
// using std::cin;
// using std::cout;
// using std::endl;

// // namespace sl
// // {
// //     class string
// //     {
// //     public:
// //         string(const char* str = "")
// //         {
// //             if(str == nullptr)
// //             {
// //                 assert(str);
// //                 return;
// //             }
// //             _str = new char[strlen(str) + 1];
// //             strcpy(_str, str);
// //         }

// //         ~string()
// //         {
// //             if(_str)
// //             {
// //                 delete[] _str;
// //                 _str = nullptr;
// //             }
// //         }

// //         void swap(string& s)
// //         {
// //             std::swap(_str, s._str);
// //         }

// //         //拷贝构造
// //         //string s2(s1);
// //         string(const string& s)
// //         {
// //             string tmp(s._str);
// //             swap(tmp);
// //         }

// //         //赋值重载
// //         string& operator=(string s)
// //         {
// //             swap(s);
// //             return *this;
// //         }
// //     private:
// //         char* _str;
// //     };
// // }

// // namespace sl
// // {
// //     class string
// //     {
// //     public:
// //         string(const char* str = " ")
// //             :_size(strlen(str))
// //             ,_capacity(_size)
// //         {
// //             _str = new char[_capacity + 1];
// //             strcpy(_str, str);
// //         }

// //         ~string()
// //         {
// //             if(_str)
// //             {
// //                 delete[] _str;
// //                 _str = nullptr;
// //                 _size = _capacity = 0;
// //             }
// //         }

// //         void swap(string& s)
// //         {
// //             std::swap(_str, s._str);
// //             std::swap(_size, s._size);
// //             std::swap(_capacity, s._capacity);
// //         }
// //         //拷贝构造
// //         //string s2(s1);
// //         string(const string& s)
// //         {
// //             string tmp(s._str);
// //             swap(tmp);
// //         }

// //         //赋值重载
// //         //s2 = s1;
// //         string& operator=(string s)
// //         {
// //             swap(s);
// //             return *this;
// //         }

// //     private:
// //         char* _str;
// //         size_t _size;
// //         size_t _capacity;
// //     };
// // }

// // namespace sl
// // {
// //     class string
// //     {
// //     public:
// //         string(const char* str = " ")
// //         {
// //             if(str == nullptr)
// //             {
// //                 assert(str);
// //                 return;
// //             }
// //             _str = new char[strlen(str) + 1];
// //             strcpy(_str, str);
// //         }

// //         ~string()
// //         {
// //             if(_str)
// //             {
// //                 delete[] _str;
// //                 _str = nullptr;
// //             }
// //         }

// //         void swap(string& s)
// //         {
// //             std::swap(_str, s._str);
// //         }

// //         string(const string& s)
// //         {
// //             string tmp(s._str);
// //             swap(tmp);
// //         }

// //         string& operator=(string s)
// //         {
// //             swap(s);
// //             return *this;
// //         }
// //     private:
// //         char* _str;
// //     };
// // }

// // namespace sl
// // {
// //     class string
// //     {
// //         typedef char* iterator;
// //         typedef const char* const_iterator;
// //     public:
// //         string(const char* str = " ")
// //             :_size(strlen(str))
// //             ,_capacity(_size)
// //         {
// //             _str = new char[_capacity + 1];
// //             strcpy(_str, str);
// //         }

// //         ~string()
// //         {
// //             if(_str)
// //             {
// //                 delete[] _str;
// //                 _str = nullptr;
// //                 _size = _capacity = 0;
// //             }
// //         }

// //         void swap(string& s)
// //         {
// //             std::swap(_str, s._str);
// //             std::swap(_size, s._size);
// //             std::swap(_capacity, s._capacity);
// //         }

// //         string(const string& s)
// //         {
// //             string tmp(s._str);
// //             swap(tmp);
// //         }

// //         string& operator=(string s)
// //         {
// //             swap(s);
// //             return *this;
// //         }

// //         iterator begin()
// //         {
// //             return _str;
// //         }

// //         iterator end()
// //         {
// //             return _str + _size;
// //         }

// //         const_iterator begin()const
// //         {
// //             return _str;
// //         }

// //         const_iterator end()const
// //         {
// //             return _str + _size;
// //         }

// //         size_t size()const
// //         {
// //             return _size;
// //         }

// //         size_t capacity()const
// //         {
// //             return _capacity;
// //         }

// //         const char* c_str()const
// //         {
// //             return _str;
// //         }

// //         char& operator[](size_t pos)
// //         {
// //             assert(pos < _size);
// //             return _str[pos];
// //         }

// //         const char& operator[](size_t pos)const
// //         {
// //             assert(pos < _size);
// //             return _str[pos];
// //         }

// //         void reserve(size_t n)
// //         {
// //             if(n > _capacity)
// //             {
// //                 char* tmp = new char[n + 1];
// //                 strcpy(tmp, _str);
// //                 delete[] _str;
// //                 _str = tmp;
// //                 _capacity = n;
// //             }
// //         }

// //         void resize(size_t n, char ch = '\0')
// //         {
// //             if(n < _size)
// //             {
// //                 _size = n;
// //                 _str[_size] = '\0';//需要单独处理'\0'
// //             }
// //             else
// //             {
// //                 if(n > _capacity)
// //                 {
// //                     reserve(n);
// //                 }
// //                 for(size_t i = _size; i < n; i++)
// //                 {
// //                     _str[i] = ch;
// //                 }
// //                 _size = n;
// //                 _str[_size] = '\0';
// //             }
// //         }

// //         void push_back(char ch)
// //         {
// //             if(_size == _capacity)
// //             {
// //                 reserve(_capacity == 0 ? 4 : _capacity * 2);
// //             }
// //             _str[_size] = ch;
// //             _size++;
// //             _str[_size] = '\0';
// //         }

// //         string& operator+=(char ch)
// //         {
// //             push_back(ch);
// //             return *this;
// //         }

// //         void append(const char* str)
// //         {
// //             size_t len = _size + strlen(str);
// //             if(len > _capacity)
// //             {
// //                 reserve(len);
// //             }
// //             strcpy(_str + _size, str);
// //             _size = len;
// //         }

// //         string& operator+=(const char* str)
// //         {
// //             append(str);
// //             return *this;
// //         }

// //         bool operator==(const string& s)
// //         {
// //             return strcmp(c_str(), s.c_str()) == 0;
// //         }

// //     private:
// //         char* _str;
// //         size_t _size;
// //         size_t _capacity;
// //     };
// // }

// // namespace sl
// // {
// //     template<class T>
// //     class string
// //     {
// //     public:
// //         string(const char* str = " ")
// //         {
// //             if(str == nullptr)
// //             {
// //                 assert(str);
// //                 return;
// //             }
// //             _str = new char[strlen(str) + 1];
// //             strcpy(_str, str);
// //         }

// //         ~string()
// //         {
// //             if(_str)
// //             {
// //                 delete[] _str;
// //                 _str = nullptr;
// //             }
// //         }

// //         void swap(string& s)
// //         {
// //             std::swap(_str, s._str);
// //         }

// //         string(const string& s)
// //         {
// //             string tmp(s._str);
// //             swap(tmp);
// //         }

// //         string& operator=(string s)
// //         {
// //             swap(s);
// //             return *this;
// //         }
// //     private:
// //         char* _str;

// //     };
// // }

// // namespace sl
// // {
// //     class string
// //     {
// //     public:
// //         string(const char* str = " ")
// //         {
// //             if(str == nullptr)
// //             {
// //                 assert(str);
// //                 return;
// //             }

// //             _str = new char[strlen(str) + 1];
// //             strcpy(_str, str);
// //         }

// //         ~string()
// //         {
// //             if(_str)
// //             {
// //                 delete[] _str;
// //                 _str = nullptr;
// //             }
// //         }

// //         void swap(string& s)
// //         {
// //             std::swap(_str, s._str);
// //         }

// //         string(const string& s)
// //         {
// //             string tmp(s._str);
// //             swap(tmp);
// //         }

// //         string& operator=(string s)
// //         {
// //             swap(s);
// //             return *this;
// //         }

// //         const char* c_str()const
// //         {
// //             return _str;
// //         }

// //         size_t size()const
// //         {
// //             return strlen(_str);
// //         }

// //         char& operator[](size_t pos)
// //         {
// //             return _str[pos];
// //         }

// //     private:
// //         char* _str;
// //     };
// // }

// // namespace sl
// // {
// //     class string
// //     {
// //     public:
// //         typedef char* iterator;
// //         typedef const char* const_iterator;

// //         string(const char* str = " ")
// //             :_size(strlen(str))
// //             ,_capacity(_size)
// //         {
// //             _str = new char[_capacity + 1];
// //             strcpy(_str, str);
// //         }

// //         ~string()
// //         {
// //             if(_str)
// //             {
// //                 delete[] _str;
// //                 _str = nullptr;
// //                 _size = _capacity = 0;
// //             }
// //         }

// //         void swap(string& s)
// //         {
// //             std::swap(_str, s._str);
// //             std::swap(_size, s._size);
// //             std::swap(_capacity, s._capacity);
// //         }

// //         string(const string& s)
// //         {
// //             string tmp(s._str);
// //             swap(tmp);
// //         }

// //         string& operator=(string s)
// //         {
// //             swap(s);
// //             return *this;
// //         }

// //         iterator begin()
// //         {
// //             return _str;
// //         }

// //         iterator end()
// //         {
// //             return _str + _size;
// //         }

// //         const_iterator begin()const
// //         {
// //             return _str;
// //         }

// //         const_iterator end()const
// //         {
// //             return _str + _size;
// //         }

// //         void reserve(size_t n)
// //         {
// //             if(n > _capacity)
// //             {
// //                 char* tmp = new char[n + 1];
// //                 strcpy(tmp, _str);
// //                 delete[] _str;
// //                 _str = tmp;
// //                 _capacity = n;
// //             }
// //         }

// //         void resize(size_t n, char ch = '\0')
// //         {
// //             if(n < _size)
// //             {
// //                 _size = n;
// //                 _str[_size] = '\0';//需要单独处理'\0'
// //             }
// //             else
// //             {
// //                 if(n > _capacity)
// //                 {
// //                     reserve(n);
// //                 }
// //                 for(size_t i = _size; i < n; i++)
// //                 {
// //                     _str[i] = ch;
// //                 }
// //                 _size = n;
// //                 _str[_size] = '\0';
// //             }
// //         }
// //     private:
// //         char* _str;
// //         size_t _size;
// //         size_t _capacity;
// //     };
// // }

// // namespace sl
// // {
// //     class string
// //     {
// //     public:
// //         string(const char* str = " ")
// //         {
// //             if(str == nullptr)
// //             {
// //                 assert(str);
// //                 return;
// //             }
// //             _str = new char[strlen(str) + 1];
// //             strcpy(_str, str);
// //         }

// //         ~string()
// //         {
// //             if(_str)
// //             {
// //                 delete[] _str;
// //                 _str = nullptr;
// //             }
// //         }

// //         void swap(string& s)
// //         {
// //             std::swap(_str, s._str);
// //         }

// //         string(const string& s)
// //         {
// //             string tmp(s._str);
// //             swap(tmp);
// //         }

// //         string& operator=(string s)
// //         {
// //             swap(s);
// //             return *this;
// //         }

// //     private:
// //         char* _str;
// //     };
// // }

// // namespace sl
// // {
// //     class string
// //     {
// //     public:
// //         string(const char* str = " ")
// //             :_size(strlen(str))
// //             ,_capacity(_size)
// //         {
// //             _str = new char[_capacity + 1];
// //             strcpy(_str, str);
// //         }

// //         ~string()
// //         {
// //             if(_str)
// //             {
// //                 delete[] _str;
// //                 _str = nullptr;
// //                 _size = _capacity = 0;
// //             }
// //         }

// //         void swap(string& s)
// //         {
// //             std::swap(_str, s._str);
// //             std::swap(_size, s._size);
// //             std::swap(_capacity, s._capacity);
// //         }

// //         string(const string& s)
// //         {
// //             string tmp(s._str);
// //             swap(tmp);
// //         }

// //         string& operator=(string& s)
// //         {
// //             swap(s);
// //             return *this;
// //         }
// //     private:
// //         char* _str;
// //         size_t _size;
// //         size_t _capacity;
// //     };
// // }

// // namespace sl
// // {
// //     class string
// //     {
// //     public:
// //         string(const char* str)
// //         {
// //             if(str == nullptr)
// //             {
// //                 assert(str);
// //                 return;
// //             }
// //             _str = new char[strlen(str) + 1];
// //             strcpy(_str, str);
// //         }

// //         ~string()
// //         {
// //             if(_str)
// //             {
// //                 delete[] _str;
// //                 _str = nullptr;
// //             }
// //         }

// //         void swap(string& s)
// //         {
// //             std::swap(_str, s._str);
// //         }

// //         string(const string& s)
// //              :_str(nullptr)
// //         {
// //             string tmp(s._str);
// //             swap(tmp);
// //         }

// //         string& operator=(string s)
// //         {
// //             swap(s);
// //             return *this;
// //         }
// //     private:
// //         char* _str;
// //     };
// // }

// namespace sl
// {
//     class string
//     {
//     public:

//         typedef char* iterator;
//         typedef const char* const_iterator;

//         string(const char* str = " ")
//             :_size(strlen(str))
//             ,_capacity(_size)
//         {
//             _str = new char[_capacity + 1];
//             strcpy(_str, str);
//         }

//         ~string()
//         {
//             if(_str)
//             {
//                 delete[] _str;
//                 _str = nullptr;
//                 _size = _capacity = 0;
//             }
//         }

//         void swap(string& s)
//         {
//             std::swap(_str, s._str);
//             std::swap(_size, s._size);
//             std::swap(_capacity, s._capacity);
//         }

//         string(const string& s)
//             :_str(nullptr)
//             ,_size(0)
//             ,_capacity(0)
//         {
//             string tmp(s._str);
//             swap(tmp);
//         }

//         string& operator=(string s)
//         {
//             swap(s);
//             return *this;
//         }

//     private:
//         char* _str;
//         size_t _size;
//         size_t _capacity;
//     };
// }

//#include<cassert>
// #include<cstring>
// #include<algorithm>

// class string
// {
// public:
//     //构造函数
//     string(const char* str = " ")
//     {
//         if(str == nullptr)
//         {
//             assert(str);
//             return;
//         }
//         _str = new char[strlen(str) + 1];
//         strcpy(_str, str);
//     }

//     //析构函数
//     ~string()
//     {
//         if(_str)
//         {
//             delete[] _str;
//             _str = nullptr;
//         }
//     }

//     //拷贝构造
//     //过时写法
//     // string(const string& s)
//     //     :_str(new char[strlen(s._str) + 1])
//     // {
//     //     strcpy(_str, s._str);
//     // }

//     //现代写法
//     void swap(string& s)
//     {
//         std::swap(_str, s._str);
//     }

//     string(const string& s)
//         :_str(nullptr)
//     {
//         string tmp(s._str);
//         swap(tmp);
//     }

//     //赋值重载
//     //过时写法
//     // string& operator=(const string& s)
//     // {
//     //     if(this != &s)
//     //     {
//     //         char* tmp = new char[strlen(s._str) + 1];
//     //         strcpy(tmp, _str);
//     //         delete[] _str;
//     //         _str = tmp;
//     //     }
//     //     return *this;
//     // }

//     //现代写法
//     string& operator=(string s)
//     {
// //         swap(s);
// //         return *this;
// //     }

// // private:
// //     char* _str;
// // };

// #include <iostream>
// #include <cstring>
// #include <algorithm>
// #include <cassert>
// #include <string>
// using std::cin;
// using std::cout;
// using std::endl;
// using std::string;
// using std::istream;
// using std::ostream;

// namespace sl
// {
//     class string
//     {
//     public:
//         typedef char *iterator;
//         typedef const char *const_iterator;

//         //构造函数
//         string(const char *str = " ")
//             : _size(strlen(str)), _capacity(_size)
//         {
//             _str = new char[_capacity + 1]; //+1是因为始终要为'\0'多开一个空间
//             strcpy(_str, str);
//         }

//         //析构函数
//         ~string()
//         {
//             if (_str)
//             {
//                 delete[] _str;
//                 _str = nullptr;
//                 _size = _capacity = 0;
//             }
//         }

//         void swap(string &s)
//         {
//             std::swap(_str, s._str);
//             std::swap(_size, s._size);
//             std::swap(_capacity, s._capacity);
//         }

//         //拷贝构造
//         string(const string &s)
//             : _str(nullptr), _size(0), _capacity(0)
//         {
//             string tmp(s._str);
//             swap(tmp);
//         }

//         //赋值重载
//         string &operator=(string s)
//         {
//             swap(s);
//             return *this;
//         }

//         iterator begin()
//         {
//             return _str;
//         }

//         iterator end()
//         {
//             return _str + _size;
//         }

//         const_iterator begin() const
//         {
//             return _str;
//         }

//         const_iterator end() const
//         {
//             return _str + _size;
//         }

//         size_t size() const
//         {
//             return _size;
//         }

//         size_t capacity() const
//         {
//             return _capacity;
//         }

//         void reserve(size_t n)
//         {
//             if (n > capacity())
//             {
//                 char *tmp = new char[n + 1];
//                 strcpy(tmp, _str);
//                 delete[] _str;
//                 _str = tmp;

//                 _capacity = n;
//             }
//         }

//         void resize(size_t n, char ch = '\0')
//         {
//             if (n < _size)
//             {
//                 _size = n;
//                 _str[_size] = ch;
//             }
//             else
//             {
//                 if (n > _capacity)
//                 {
//                     reserve(n);
//                 }
//                 for (size_t i = _size; i < n; i++)
//                 {
//                     _str[i] = ch;
//                 }
//                 _size = n;
//                 _str[_size] = '\0';
//             }
//         }

//         void push_back(char ch)
//         {
//             if (_size == _capacity)
//             {
//                 reserve(_capacity == 0 ? 4 : _capacity * 2);
//             }

//             _str[_size] = ch;
//             _size++;
//             _str[_size] = '\0'; // string与顺序表不同, 要单独处理末尾的'\0'
//         }

//         string &operator+=(char ch)
//         {
//             push_back(ch);
//             return *this;
//         }

//         //注意追加一个字符串不同于追加一个字符, 需要小心处理
//         void append(const char *str)
//         {
//             size_t len = _size + strlen(str);
//             if (len > _capacity)
//             {
//                 reserve(len);
//             }
//             strcpy(_str + _size, str);
//             _size = len;
//         }

//         string &operator+=(const char *str)
//         {
//             append(str);
//             return *this;
//         }

//         const char *c_str() const
//         {
//             return _str;
//         }

//         //随机插入
//         string &insert(size_t pos, char ch)
//         {
//             assert(pos <= _size);

//             if (_size == _capacity)
//                 reserve(_capacity == 0 ? 4 : _capacity * 2);

//             size_t end = _size + 1; //注意, 遇到size_t时处理起来要格外小心
//             while (end > pos)
//             {
//                 _str[end] = _str[end - 1];
//                 end--;
//             }
//             _str[pos] = ch;
//             _size++;

//             return *this;
//         }

//         //随机插入
//         string &insert(size_t pos, const char *str)
//         {
//             assert(pos <= _size);

//             size_t len = strlen(str);
//             if (_size + len > _capacity)
//             {
//                 reserve(_size + len);
//             }

//             //往后挪 len 个位置
//             //注意这个过程较复杂需要画图理解
//             size_t end = _size + len;
//             while (end > pos + len - 1) //注意这个循环条件
//             {
//                 _str[end] = _str[end - len];
//                 end--;
//             }
//             strncpy(_str + pos, str, len); // strcpy()会拷贝'\0'
//             _size += len;

//             return *this;
//         }

//         //随机删除
//         string &erase(size_t pos, size_t len = std::string::npos) //注意哦
//         {
//             assert(pos < _size);

//             if (len == std::string::npos || len + pos >= _size)
//             {
//                 _str[pos] = '\0';
//                 _size = pos;
//             }
//             else
//             {
//                 size_t begin = pos + len;
//                 while (begin <= _size) //注意判断循环条件
//                 {
//                     _str[begin - len] = _str[begin];
//                     begin++;
//                 }
//                 _size -= len;
//             }
//             return *this;
//         }

//     private:
//         char *_str;
//         size_t _size;
//         size_t _capacity;
//     };
// }

//         return *this;
//     }

// private:
//     char* _str;
// };

// #include <iostream>
// #include <cstring>
// #include <algorithm>
// #include <cassert>
// #include <string>
// using std::cin;
// // using std::cout;
// using std::endl;
// using std::istream;
// using std::ostream;
// using std::string;

// namespace sl
// {
//     class string
//     {
//     public:
//         typedef char *iterator;
//         typedef const char *const_iterator;

//         //构造函数
//         string(const char *str = " ")
//             : _size(strlen(str)), _capacity(_size)
//         {
//             _str = new char[_capacity + 1]; //+1是因为始终要为'\0'多开一个空间
//             strcpy(_str, str);
//         }

//         //析构函数
//         ~string()
//         {
//             if (_str)
//             {
//                 delete[] _str;
//                 _str = nullptr;
//                 _size = _capacity = 0;
//             }
//         }

//         void swap(string &s)
//         {
//             std::swap(_str, s._str);
//             std::swap(_size, s._size);
//             std::swap(_capacity, s._capacity);
//         }

//         //拷贝构造
//         string(const string &s)
//             : _str(nullptr), _size(0), _capacity(0)
//         {
//             string tmp(s._str);
//             swap(tmp);
//         }

//         //赋值重载
//         string &operator=(string s)
//         {
//             swap(s);
//             return *this;
//         }

//         iterator begin()
//         {
//             return _str;
//         }

//         iterator end()
//         {
//             return _str + _size;
//         }

//         const_iterator begin() const
//         {
//             return _str;
//         }

//         const_iterator end() const
//         {
//             return _str + _size;
//         }

//         void clear()
//         {
//             _str[0] = '\0';
//             _size = 0;//不必释放空间
//         }

//     private:
//         char *_str;
//         size_t _size;
//         size_t _capacity;
//     };
// }
// //流插入
// //不需要设计成友元函数, 因为没有访问私有成员
// ostream &operator<<(ostream &out, const string &s)
// {
//     for (auto &e : s)
//     {
//         out << e;
//     }
//     return out;
// }

// //流提取
// // istream& operator>>(istream& in, string& s)
// // {
// //     char ch;
// //     //in >> ch;//注意cin不能读取到空格和换行
// //     ch = in.get();//get()便是从流中提取字符
// //     while(ch != ' ' && ch != '\n')
// //     {
// //         s += ch;
// //         ch = in.get();
// //     }

// //     return in;
// // }

// //上面实现的流提取不够高效, 原因在于会频繁插入数据导致经常扩容影响效率
// //优化
// //流提取
// istream &operator>>(istream &in, string &s)
// {
//     s.clear(); //将数据全部清理掉

//     char ch;
//     ch = in.get();
//     char buff[128] = {'\0'};
//     size_t i = 0;
//     while(ch != '\n')
//     {
//         buff[i++] = ch;
//         if(i == 127)
//         {
//             s += buff;
//             memset(buff, '\0', 128);
//             i = 0;
//         }
//         ch = in.get();
//     }
//     s += buff;
    
//     return in;
// }

// #include<cstdio>
// #include<cstring>
// #include<algorithm>

// namespace sl
// {
//     class string
//     {
//     public:
//         typedef char* iterator;
//         typedef const char* const_iterator;

//         string(const char* str = " ")
//             :_size(strlen(str))
//             ,_capacity(_size)
//         {
//             _str = new char[_capacity + 1];
//             strcpy(_str, str);
//         }

//         void swap(string& s)
//         {
//             std::swap(_str, s._str);
//             std::swap(_size, s._size);
//             std::swap(_capacity, s._capacity);
//         }

//         string(const string& s)
//             :_size(s._size)
//             ,_capacity(_size)
//         {
//             string tmp(s._str);
//             swap(tmp);
//         }

//         string& operator=(string s)
//         {
//             swap(s);
//             return *this;
//         }

//     private:
//         char* _str;
//         size_t _size;
//         size_t _capacity;
//     };
// }


// #include<iostream>
// #include<cstring>
// using std::cin;
// using std::cout;
// using std::endl;


// namespace sl
// {
//     class string
//     {
//     public:
//         string(const char* str = " ")
//             :_str(new char[strlen(str) + 1])
//         {
//             strcpy(_str, str);
//         }

//         ~string()
//         {
//             if(_str)
//             {
//                 delete[] _str;
//                 _str = nullptr;
//             }
//         }

//         void swap(string s)
//         {
//             std::swap(_str, s._str);
//         }

//         string(const string& s)
//         {
//             string tmp(s._str);
//             swap(s);
//         }

//         string& operator=(string s)
//         {
//             swap(s);
//             return *this;
//         }

//     private:
//         char* _str;
//     };
// }


// #include<cassert>
// #include<cstring>
// #include<iostream>
// #include<algorithm>
// using std::cout;
// using std::endl;

// namespace sl
// {
//     class string
//     {
//     public:
//         string(const char* str = " ")
//         {
//             if(str == nullptr)
//             {
//                 assert(str);
//                 return;
//             }
//             _str = new char[strlen(str) + 1];
//             strcpy(_str, str);
//         }

//         ~string()
//         {
//             if(_str)
//             {
//                 delete[] _str;
//                 _str = nullptr;
//             }
//         }

//         void swap(string& s)
//         {
//             std::swap(_str, s._str);
//         }

//         string(const string& s)
//         {
//             string tmp(s._str);
//             swap(tmp);
//         }

//         string& operator=(string s)
//         {
//             swap(s);
//             return *this;
//         }
//     private:
//         char* _str;
//     };
// }

// #include<iostream>
// #include<cassert>
// #include<cstring>
// #include<algorithm>

// namespace sl
// {
//     class string
//     {
//     public:
//         string(const char* str = " ")
//         {
//             if(str == nullptr)
//             {
//                 assert(str);
//                 str = nullptr;
//             }
//             _str = new char[strlen(str) + 1];
//             strcpy(_str, str);
//         }

//         ~string()
//         {
//             if(_str)
//             {
//                 delete[] _str;
//                 _str = nullptr;
//             }
//         }

//         void swap(string& s)
//         {
//             std::swap(_str, s._str);
//         }

//         string(const string& s)
//         {
//             string tmp(s._str);
//             swap(tmp);
//         }

//         string& operator=(string s)
//         {
//             swap(s);
//             return *this;
//         }

//     private:
//         char* _str;
//     };
// }

// 节点类
template<class T>
struct _list_node
{
    typedef _list_node<T> node;

    T _val;
    node* _prev;
    node* _next;

    _list_node(const T& val)
        : _val(val)
        , _prev(nullptr)
        , _next(nullptr)
    {}
};

// 迭代器类
template<class T, class Ref, class Ptr>
struct _list_iterator
{
    typedef _list_node<T> node;
    typedef _list_iterator<T, Ref, Ptr> self;

    node* _node;

    _list_iterator(node* pnode)
        : _node(pnode)
    {}

    self& operator++()
    {
        _node = _node->_next;
        return *this;
    }

    self operator++(int)
    {
        self tmp(*this);
        _node = _node->_next;
        return tmp;
    }

    self& operator--()
    {
        _node = _node->_prev;
        return *this;
    }

    self operator--(int)
    {
        self tmp(*this);
        _node = _node->_prev;
        return tmp;
    }

    bool operator==(const self& lt) const
    {
        return _node == lt._node;
    }

    bool operator!=(const self& lt) const
    {
        return _node != lt._node;
    }

    Ref operator*()
    {
        return _node->_val;
    }

    Ptr operator->()
    {
        return &_node->_val;
    }
};  


// List类
template<class T>
class List
{
public:
    typedef _list_node<T> node;
    typedef _list_iterator<T, T&, T*> iterator;
    typedef _list_iterator<const T, const T&, const T*> const_iterator;

    node* _head;

    List()
    {
        _head = new node();
        _head->_prev = _head;
        _head->_next = _head;
    }

    void head_init()
    {
        _head = new node();
        _head->_prev = _head;
        _head->_next = _head;
    }

    // 迭代器区间构造
    template<class InputIterator>
    List(InputIterator first, InputIterator last)
    {
        head_init();

        while(first != last)
        {
            push_back(*first);
            first++;
        }
    }

    // List(const List<T>& lt)
    // {
    //     head_init();

    //     for(const auto& e : lt)
    //         push_back(e);
    // }

    void swap(List<T>& lt)
    {
        std::swap(_head, lt._head);
    }

    List(const List<T>& lt)
    {
        head_init();

        List<T> tmp(lt.begin(), lt.end());
        swap(tmp);
    }

    // List<T>& operator=(const List<T>& lt)
    // {
    //     if(this != &lt)
    //     {
    //         clear();

    //         for(const auto& e : lt)
    //         {
    //             push_back(e);
    //         }
    //     }

    //     return *this;
    // }

    List<T>& operator=(List<T> lt)
    {
        swap(lt);
        return *this;
    }

    ~List()
    {
        clear();

        delete _head;
        _head = nullptr;
    }

    void clear()
    {
        iterator it = begin();

        while(it != end())
        {
            it = erase(it);
        }
    }

    // 迭代器相关函数
    iterator begin()
    {
        return iterator(_head->_next);
    }

    iterator end()
    {
        return iterator(_head);
    }

    const_iterator begin() const
    {
        return const_iterator(_head->_next);
    }

    const_iterator end() const
    {
        return const_iterator(_head);
    }

    // 容器操作函数
    T& front()
    {
        return *beign();
    }

    T& back()
    {
        return *(--end());
    }

    const T& front() const
    {
        return *begin();
    }

    const T& back() const
    {
        return *(--end());
    }

    // 随机插入 / 删除函数
    void insert(iterator pos, const T& val)
    {
        assert(pos->_node);

        node* newnode = new node(val);

        node* cur = pos->_node;
        node* prev = cur->_prev;

        newnode->_next = cur;
        cur->_prev = newnode;

        newnode->_prev = prev;
        prev->_next = newnode;
    }

    iterator erase(iterator pos)
    {
        assert(pos->_node);
        assert(pos != end());

        node* cur = pos->_node;
        node* prev = cur->_prev;
        node* next = cur->_next;

        delete cur;

        prev->_next = next;
        next->_prev = prev;

        return iterator(next);
    }

    void push_back(const T& val)
    {
        insert(end(), val);
    }
};



class string
{
private:
    char* _str;

public:
    string(const char* str = "")
    {
        if(nullptr == str)
        {
            assert(str);
            return;
        }

        _str = new char[strlen(str) + 1];
        strcpy(_str, str);
    }

    void swap(string& s)
    {
        std::swap(_str, s._str);
    }

    string(const string& s)
        : _str(nullptr)
    {
        string tmp(s._str);
        swap(tmp);
    }

    string& operator=(string s)
    {
        swap(s);
        return *this;
    }

    ~string()
    {
        if(_str)
        {
            delete[] _str;
            _str = nullptr;
        }
    }
};


